#include<vector>
#include<stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    void recoverTree(TreeNode* root) {
        if (root == NULL) return;
        TreeNode* prev = NULL;
        TreeNode* cur = NULL;
        TreeNode* first = NULL, *second = NULL, *secondTMP=NULL;

        stack<TreeNode*> stack_;
        while (root != NULL) {
            stack_.push(root);
            root = root->left;
        }
        while (!stack_.empty()) {
            cur = stack_.top();
            stack_.pop();
            if (prev != NULL) {
                if (prev->val > cur->val) {
                    if (first == NULL) {
                        first = prev;
                        secondTMP = cur;
                    }
                    else if (second == NULL) {
                        second = cur;
                    }
                    else
                        break;
                }
            }
            prev = cur;
            cur = cur->right;
            while (cur != NULL) {
                stack_.push(cur);
                cur = cur->left;
            }
        }
        if (second == NULL)
            second = secondTMP;
        swap(first->val, second->val);
    }
};